#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48,ch=getchar();}
	return x*f;
}
#define fi first
#define sd second

int T,n,m,to[N],ans=1e18;
pair<int,int> e[N],p[N];
bool hv[N];
bool vis[N][N];
int gt[N];

void dfs(int pos){
	if(pos==n+1){
		int res=0,cntp=0;
		for(int i=1;i<=m;i++) p[i]=e[i];
		for(int i=1;i<=n;i++){
			if(hv[i]){
				for(int j=1;j<=m;j++){
					if(p[j].fi==i) p[j].fi=to[i];
					if(p[j].sd==i) p[j].sd=to[i];
				}
			}
			else cntp++;
		}
		int cnte=0;
		for(int i=1;i<=m;i++){
			if(!vis[p[i].fi][p[i].sd]){
				vis[p[i].fi][p[i].sd]=1;
				gt[p[i].fi]=p[i].sd;
			}
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				vis[i][j]=0;
		for(int i=1;i<=n;i++) gt[i]=0;
		return;
	}
	for(int i=1;i<=n;i++){
		if(i==pos) dfs(pos+1);
		else{
			hv[pos]=1;
			if(!hv[i]) to[pos]=i,dfs(pos+1);
			hv[pos]=0;
		}
	}
}

signed main(){
	freopen("circ.in","r",stdin);
	freopen("circ.out","w",stdout);
	T=read();
	while(T--){
		n=read(),m=read();
		for(int i=1;i<=m;i++){
			int u=read(),v=read();
			e[i]={u,v};
		}
		dfs(1);
		printf("%lld\n",ans);
	}
    return 0;
}